home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / smail-3.1.28 / pd / pathalias / addnode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-03  |  8.9 KB  |  393 lines
  1. /* Smail SCCS ID: @(#)pd/pathalias/addnode.c    1.3 11/4/91 05:29:56 */
  2. /* pathalias -- by steve bellovin, as told to peter honeyman */
  3. #ifndef lint
  4. static char    *sccsid = "@(#)addnode.c    9.6 89/05/05";
  5. #endif
  6.  
  7. #include "def.h"
  8.  
  9. #define EQ(n, s)    (*(n)->n_name == *(s) && strcmp((n)->n_name, (s)) == 0)
  10.  
  11. /* exports */
  12. node *addnode(), *addprivate();
  13. void alias(), hashanalyze(), fixprivate();
  14. node **Table;                /* hash table ^ priority queue */
  15. long Tabsize;                /* size of Table */    
  16.  
  17. /* imports */
  18. extern link *addlink();
  19. extern node *newnode(), **newtable();
  20. extern char *strsave();
  21. extern int Iflag, Tflag, Vflag;
  22. extern node **Table;
  23. extern long Ncount, Tabsize;
  24. extern char **Argv;
  25. extern void atrace(), die(), freetable();
  26. #ifndef SMAIL_3
  27. extern int strcmp();
  28. #endif
  29.  
  30. /* privates */
  31. STATIC void crcinit(), rehash(), lowercase();
  32. STATIC long fold();
  33. STATIC long hash();
  34. STATIC node *isprivate();
  35. static node *Private;    /* list of private nodes in current input file */
  36. /*
  37.  * these numbers are chosen because:
  38.  *    -> they are prime,
  39.  *    -> they are monotonic increasing,
  40.  *    -> each is a tad smaller than a multiple of 1024,
  41.  *    -> they form a fibonacci sequence (almost).
  42.  * the first point yields good hash functions, the second is used for the
  43.  * standard re-hashing implementation of open addressing, the third
  44.  * optimizes for quirks in some mallocs i have seen, and the fourth simply
  45.  * appeals to me.
  46.  */
  47. static long Primes[] = {
  48.     1021, 2039, 3067, 5113, 8179, 13309, 21499, 34807, 56311, 0
  49. };
  50.  
  51. static int    Tabindex;
  52. static long    Tab128;        /* Tabsize * 128 */
  53.  
  54. node    *
  55. addnode(name)
  56.     register char *name;
  57. {    register long i;
  58.     register node *n;
  59.  
  60.     if (Iflag)
  61.         lowercase(name);
  62.  
  63.     /* is it a private host? */
  64.     n = isprivate(name);
  65.     if (n)
  66.         return n;
  67.  
  68.     i = hash(name, 0);
  69.     if (Table[i]) 
  70.         return Table[i];
  71.  
  72.     n = newnode();
  73.     n->n_name = strsave(name);
  74.     Table[i] = n;
  75.     n->n_tloc = i;    /* essentially a back link to the table */
  76.  
  77.     return n;
  78. }
  79.  
  80. void
  81. alias(n1, n2)
  82.     node *n1, *n2;
  83. {
  84.     link    *l;
  85.  
  86.     if (ISADOMAIN(n1) && ISADOMAIN(n2)) {
  87.         fprintf(stderr, "%s: domain alias %s = %s is illegal\n", Argv[0], n1->n_name, n2->n_name);
  88.         return;
  89.     }
  90.     l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
  91.     l->l_flag |= LALIAS;
  92.     l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
  93.     l->l_flag |= LALIAS;
  94.     if (Tflag)
  95.         atrace(n1, n2);
  96. }
  97.  
  98. /*
  99.  * fold a string into a long int.  31 bit crc (from andrew appel).
  100.  * the crc table is computed at run time by crcinit() -- we could
  101.  * precompute, but it takes 1 clock tick on a 750.
  102.  *
  103.  * This fast table calculation works only if POLY is a prime polynomial
  104.  * in the field of integers modulo 2.  Since the coefficients of a
  105.  * 32-bit polynomail won't fit in a 32-bit word, the high-order bit is
  106.  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
  107.  * 31 down to 25 are zero.  Happily, we have candidates, from
  108.  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
  109.  *    x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
  110.  *    x^31 + x^3 + x^0
  111.  *
  112.  * We reverse the bits to get:
  113.  *    111101010000000000000000000000001 but drop the last 1
  114.  *         f   5   0   0   0   0   0   0
  115.  *    010010000000000000000000000000001 ditto, for 31-bit crc
  116.  *       4   8   0   0   0   0   0   0
  117.  */
  118.  
  119. #define POLY32 0xf5000000    /* 32-bit polynomial */
  120. #define POLY31 0x48000000    /* 31-bit polynomial */
  121. #define POLY POLY31    /* use 31-bit to avoid sign problems */
  122.  
  123. static long CrcTable[128];
  124.  
  125. STATIC void
  126. crcinit()
  127. {    register int i,j;
  128.     register long sum;
  129.  
  130.     for (i = 0; i < 128; i++) {
  131.         sum = 0;
  132.         for (j = 7-1; j >= 0; --j)
  133.             if (i & (1 << j))
  134.                 sum ^= POLY >> j;
  135.         CrcTable[i] = sum;
  136.     }
  137. }
  138.  
  139. STATIC long
  140. fold(s)
  141.     register char *s;
  142. {    register long sum = 0;
  143.     register int c;
  144.  
  145.     while ((c = *s++) != 0)
  146.         sum = (sum >> 7) ^ CrcTable[(sum ^ c) & 0x7f];
  147.     return sum;
  148. }
  149.  
  150.  
  151. #define HASH1(n) ((n) % Tabsize);
  152. #define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2)))    /* sedgewick */
  153.  
  154. /*
  155.  * when alpha is 0.79, there should be 2 probes per access (gonnet).
  156.  * use long constant to force promotion.  Tab128 biases HIGHWATER by
  157.  * 128/100 for reduction in strength in isfull().
  158.  */
  159. #define HIGHWATER    79L
  160. #define isfull(n)    ((n) * 128 >= Tab128)
  161.     
  162. STATIC long
  163. hash(name, unique)
  164.     char *name;
  165.     int unique;
  166. {    register long probe;
  167.     register long hash2;
  168.     register node *n;
  169.  
  170.     if (isfull(Ncount)) {
  171.         if (Tabsize == 0) {        /* first time */
  172.             crcinit();
  173.             Tabindex = 0;
  174.             Tabsize = Primes[0];
  175.             Table = newtable(Tabsize);
  176.             Tab128 = (HIGHWATER * Tabsize * 128L)/100L;
  177.         } else
  178.             rehash();        /* more, more! */
  179.     }
  180.  
  181.     probe = fold(name);
  182.     hash2 = HASH2(probe);
  183.     probe = HASH1(probe);
  184.  
  185.     /*
  186.      * probe the hash table.
  187.      * if unique is set, we require a fresh slot.
  188.      * otherwise, use double hashing to find either
  189.      *  (1) an empty slot, or
  190.      *  (2) a non-private copy of this host name
  191.      *
  192.      * this is an "inner loop."
  193.      */
  194.     while ((n = Table[probe]) != 0) {
  195.         if (EQ(n, name) && !(n->n_flag & ISPRIVATE) && !unique)
  196.             return probe;    /* this is it! */
  197.  
  198.         probe -= hash2;        /* double hashing */
  199.         if (probe < 0)
  200.             probe += Tabsize;
  201.     }
  202.     return probe;                    /* brand new */
  203. }
  204.  
  205. STATIC void
  206. rehash()
  207. {    register node **otable, **optr;
  208.     register long probe;
  209.     long osize;
  210.  
  211. #ifdef DEBUG
  212.     hashanalyze();
  213. #endif
  214.     optr = Table + Tabsize - 1;    /* ptr to last */
  215.     otable = Table;
  216.     osize = Tabsize;
  217.     Tabsize = Primes[++Tabindex];
  218.     if (Tabsize == 0)
  219.         die("too many hosts");    /* need more prime numbers */
  220.     vprintf(stderr, "rehash into %d\n", Tabsize);
  221.     Table = newtable(Tabsize);
  222.     Tab128 = (HIGHWATER * Tabsize * 128L)/100L;
  223.  
  224.     do {
  225.         if (*optr == 0)
  226.             continue;    /* empty slot in old table */
  227.         probe = hash((*optr)->n_name,
  228.             ((*optr)->n_flag & ISPRIVATE) != 0);
  229.         if (Table[probe] != 0)
  230.             die("rehash error");
  231.         Table[probe] = *optr;
  232.         (*optr)->n_tloc = probe;
  233.     } while (optr-- > otable);
  234.     freetable(otable, osize);
  235. }
  236.  
  237. void
  238. hashanalyze()
  239. #if 0
  240. {     long    probe, hash2;
  241.     int    count, i, collision[8];
  242.     int    longest = 0, total = 0, slots = 0, longprobe = 0;
  243.     int    nslots = sizeof(collision)/sizeof(collision[0]);
  244.  
  245.     if (!Vflag)
  246.         return;
  247.  
  248.     strclear((char *) collision, sizeof(collision));
  249.     for (i = 0; i < Tabsize; i++) {
  250.         if (Table[i] == 0)
  251.             continue;
  252.         /* private hosts too hard to account for ... */
  253.         if (Table[i]->n_flag & ISPRIVATE)
  254.             continue;
  255.         count = 1;
  256.         probe = fold(Table[i]->n_name);
  257.         /* don't change the order of the next two lines */
  258.         hash2 = HASH2(probe);
  259.         probe = HASH1(probe);
  260.         /* thank you! */
  261.         while (Table[probe] != 0
  262.             && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
  263.             count++;
  264.             probe -= hash2;
  265.             if (probe < 0)
  266.                 probe += Tabsize;
  267.         }
  268.         if (Table[probe] == 0)
  269.             die("impossible hash error");
  270.         
  271.         total += count;
  272.         slots++;
  273.         if (count > longest) {
  274.             longest = count;
  275.             longprobe = i;
  276.         }
  277.         if (count >= nslots)
  278.             count = 0;
  279.         collision[count]++;
  280.     }
  281.     for (i = 1; i < nslots; i++)
  282.         if (collision[i])
  283.             fprintf(stderr, "%d chains: %d (%ld%%)\n",
  284.                 i, collision[i], (collision[i] * 100L)/ slots);
  285.         if (collision[0])
  286.             fprintf(stderr, "> %d chains: %d (%ld%%)\n",
  287.                 nslots - 1, collision[0],
  288.                 (collision[0] * 100L)/ slots);
  289.     fprintf(stderr, "%2.2f probes per access, longest chain: %d, %s\n",
  290.         (double) total / slots, longest, Table[longprobe]->n_name);
  291.     if (Vflag < 2)
  292.         return;
  293.     probe = fold(Table[longprobe]->n_name);
  294.     hash2 = HASH2(probe);
  295.     probe = HASH1(probe);
  296.     while (Table[probe] != 0
  297.         && strcmp(Table[probe]->n_name, Table[longprobe]->n_name) != 0) {
  298.         fprintf(stderr, "%5d %s\n", probe, Table[probe]->n_name);
  299.         probe -= hash2;
  300.         if (probe < 0)
  301.             probe += Tabsize;
  302.     }
  303.     fprintf(stderr, "%5d %s\n", probe, Table[probe]->n_name);
  304.     
  305. }
  306. #else
  307. {
  308.     /* the hash algorithms are perfect -- leave them alone */
  309. }
  310. #endif
  311.  
  312. /* convert to lower case in place */
  313. STATIC void
  314. lowercase(s)
  315.     register char *s;
  316. {
  317.     do {
  318.         if (isupper(*s))
  319.             *s -= 'A' - 'a';    /* ASCII */
  320.     } while (*s++);
  321. }
  322.  
  323. /*
  324.  * this might need change if privates catch on
  325.  */
  326. STATIC node *
  327. isprivate(name)
  328.     register char *name;
  329. {    register node *n;
  330.  
  331.     for (n = Private; n != 0; n = n->n_private)
  332.         if (strcmp(name, n->n_name) == 0)
  333.             return n;
  334.     return 0;
  335. }
  336.  
  337. /*  Add a private node so private that nobody can find it.  */
  338. node *
  339. addhidden(name)
  340.     register char *name;
  341. {    register node *n;
  342.     register int i;
  343.     if (Iflag)
  344.         lowercase(name);
  345.  
  346.     n = newnode();
  347.     n->n_name = strsave(name);
  348.     n->n_flag = ISPRIVATE;
  349.     i = hash(n->n_name, 1);
  350.     if (Table[i] != 0)
  351.         die("impossible hidden node error");
  352.     Table[i] = n;
  353.     n->n_tloc = i;
  354.     n->n_private = 0;
  355.     return n;
  356. }
  357.  
  358. void
  359. fixprivate()
  360. {    register node *n, *next;
  361.     register long i;
  362.  
  363.     for (n = Private; n != 0; n = next) {
  364.         n->n_flag |= ISPRIVATE;        /* overkill, but safe */
  365.         i = hash(n->n_name, 1);
  366.         if (Table[i] != 0)
  367.             die("impossible private node error");
  368.     
  369.         Table[i] = n;
  370.         n->n_tloc = i;    /* essentially a back link to the table */
  371.         next = n->n_private;
  372.         n->n_private = 0;    /* clear for later use */
  373.     }
  374.     Private = 0;
  375. }
  376.  
  377. node *
  378. addprivate(name)
  379.     register char *name;
  380. {    register node *n;
  381.  
  382.     if (Iflag)
  383.         lowercase(name);
  384.     if ((n = isprivate(name)) != 0)
  385.         return n;
  386.  
  387.     n = newnode();
  388.     n->n_name = strsave(name);
  389.     n->n_private = Private;
  390.     Private = n;
  391.     return n;
  392. }
  393.